public class PalindromeList {
    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

        public static boolean chkPalindrome(ListNode A) {
            ListNode slow = A;
            ListNode fast = A;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }

            //翻转
            ListNode end = reverse(slow, fast);
            //判断
            return check(A, end);
        }

        private static ListNode reverse(ListNode slow, ListNode fast) {
            ListNode cur = slow.next;

            while (cur != null) {
                ListNode curNext = cur.next;

                cur.next = slow;
                slow = cur;
                cur = curNext;
            }

            return slow;
        }

        private static boolean check(ListNode head, ListNode end) {
            while (head != end) {
                if (head.val != end.val) {
                    return false;
                }

                if (head.next == end){
                  return true;
                }

                head = head.next;
                end = end.next;
            }

            return true;
        }

        public static ListNode creat(){
            ListNode listNode1 = new ListNode(1);
            ListNode listNode2 = new ListNode(2);
            ListNode listNode3 = new ListNode(2);
            ListNode listNode4 = new ListNode(1);

            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;

            return listNode1;
        }

    public static void main(String[] args) {
        /*int[] arr = {1,2,3,4,5,6,7};
        Solution.rotate(arr, 3);*/

        ListNode ret = PalindromeList.creat();
        boolean ret1 = PalindromeList.chkPalindrome(ret);
        System.out.println(ret1);
    }
}
